/*
 * @lc app=leetcode.cn id=103 lang=javascript
 *
 * [103] 二叉树的锯齿形层次遍历
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
var zigzagLevelOrder = function (root) {
  if (root === null) return [];
  // 将root节点放入结果中
  const getResult = (root, k, result) => {
    if (root === null) return;
    if (k === result.length) result.push([]);
    result[k].push(root.val);

    getResult(root.left, k + 1, result);
    getResult(root.right, k + 1, result);
  };
  // 反转数组
  const reverse = (arr) => {
    for (let i = 0, j = arr.length - 1; i < j; i++, j--) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  };
  const result = [];

  getResult(root, 0, result);
  // 将偶数位的节点数组反转
  for (let i = 1; i < result.length; i += 2) {
    reverse(result[i]);
  }

  return result;
};
// @lc code=end
